{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path with Alternating Colors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestAlternatingPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #颜色交替的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数 <code>n</code>，即有向图中的节点数，其中节点标记为 <code>0</code> 到 <code>n - 1</code>。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。</p>\n",
    "\n",
    "<p>给定两个数组&nbsp;<code>redEdges</code>&nbsp;和&nbsp;<code>blueEdges</code>，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>redEdges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示图中存在一条从节点&nbsp;<code>a<sub>i</sub></code>&nbsp;到节点&nbsp;<code>b<sub>i</sub></code>&nbsp;的红色有向边，</li>\n",
    "\t<li><code>blueEdges[j] = [u<sub>j</sub>, v<sub>j</sub>]</code>&nbsp;表示图中存在一条从节点&nbsp;<code>u<sub>j</sub></code>&nbsp;到节点&nbsp;<code>v<sub>j</sub></code>&nbsp;的蓝色有向边。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回长度为 <code>n</code> 的数组&nbsp;<code>answer</code>，其中&nbsp;<code>answer[X]</code>&nbsp;是从节点&nbsp;<code>0</code>&nbsp;到节点&nbsp;<code>X</code>&nbsp;的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 <code>answer[x] = -1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, red_edges = [[0,1],[1,2]], blue_edges = []\n",
    "<strong>输出：</strong>[0,1,-1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]\n",
    "<strong>输出：</strong>[0,1,-1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= redEdges.length,&nbsp;blueEdges.length &lt;= 400</code></li>\n",
    "\t<li><code>redEdges[i].length == blueEdges[j].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>, u<sub>j</sub>, v<sub>j</sub>&nbsp;&lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-with-alternating-colors](https://leetcode.cn/problems/shortest-path-with-alternating-colors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-with-alternating-colors](https://leetcode.cn/problems/shortest-path-with-alternating-colors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[1,2]]\\n[]', '3\\n[[0,1]]\\n[[2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        ans[0] = 0\n",
    "\n",
    "        arr = [[[],[]] for _ in range(n)]\n",
    "        for x,y in redEdges:\n",
    "            arr[x][0].append(y)\n",
    "        for x,y in blueEdges:\n",
    "            arr[x][1].append(y)\n",
    "        queue = [[0,1,0],[0,0,0]]\n",
    "        while queue:\n",
    "            num,color,step = queue.pop(0)\n",
    "            while arr[num][1-color]:\n",
    "                zi = arr[num][1-color].pop(0)\n",
    "                if ans[zi] == -1:\n",
    "                    ans[zi] = step+1\n",
    "                queue.append([zi,1-color,step+1])\n",
    "                \n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        #copy\n",
    "        rg = defaultdict(list)\n",
    "        for src,dest in redEdges:\n",
    "            rg[src].append(dest)\n",
    "\n",
    "        bg = defaultdict(list)\n",
    "        for src,dest in blueEdges:\n",
    "            bg[src].append(dest) \n",
    "\n",
    "        ans= [inf]*n\n",
    "\n",
    "        def bfs():\n",
    "            q = deque([(0,True,0),(0,False,0)])\n",
    "            while q:\n",
    "                node,flag,step = q.popleft()\n",
    "                ans[node] = min(ans[node],step)\n",
    "                v = bv if flag else rv\n",
    "                v[node] = True\n",
    "\n",
    "                g= rg if flag else bg\n",
    "                v= rv if flag else bv\n",
    "                for nei in g[node]:\n",
    "                    if v[nei]:\n",
    "                        continue\n",
    "                    q.append((nei,not flag,step +1))\n",
    "        \n",
    "        bv = [False] *n\n",
    "        rv= [False]*n\n",
    "        bfs()\n",
    "        ans = [x if x!= inf else -1 for x in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        edge_r, edge_b = [set() for _ in range(n)], [set() for _ in range(n)]\n",
    "        for e in redEdges:\n",
    "            edge_r[e[0]].add(e[1])\n",
    "        for e in blueEdges:\n",
    "            edge_b[e[0]].add(e[1])\n",
    "        \n",
    "        seen_r, seen_b = set(), set()\n",
    "        seen_r.add(0)\n",
    "        seen_b.add(0)\n",
    "\n",
    "        ans = [-1] * n\n",
    "        q = [(0, 1), (0, 0)]\n",
    "        step = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node, is_red in tmp:\n",
    "                ans[node] = min(ans[node], step) if ans[node] != -1 else step\n",
    "                edges, seen = (edge_b, seen_b) if is_red else (edge_r, seen_r)\n",
    "                for e in edges[node]:\n",
    "                    if e in seen: continue\n",
    "                    seen.add(e)\n",
    "                    q.append((e, 1 - is_red))\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "        \n",
    "        dis = [-1] * n\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            level += 1\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestAlternatingPaths(self, n, redEdges, blueEdges):\n",
    "\n",
    "        len_list=[400]*(n)\n",
    "        def iter_deq():\n",
    "            while deq:\n",
    "                tmp=deq.pop()\n",
    "                idx,flag,dist=tmp\n",
    "                if (idx,flag) in visited:\n",
    "                    continue\n",
    "                visited.add((idx,flag))\n",
    "                len_list[tmp[0]]=min(len_list[tmp[0]],dist)\n",
    "                dist +=1\n",
    "                ed=redEdges if tmp[1] else blueEdges\n",
    "                for i in [p for p in ed if p[0]==tmp[0]]:\n",
    "                    idx,tflag=i[1],not flag\n",
    "                    if (idx,tflag) in visited:\n",
    "                        continue\n",
    "                    deq.insert(0,(idx,tflag,dist))\n",
    "        deq=[]\n",
    "        deq.append((0,True,0))\n",
    "        visited = set()\n",
    "        iter_deq()\n",
    "        deq=[]\n",
    "        deq.append((0,False,0))\n",
    "        visited = set()\n",
    "        iter_deq()\n",
    "        len_list=[p if p!=400 else -1 for p in len_list]\n",
    "        return len_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        #建图：\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in redEdges:    #从节点a走红色边到达节点b\n",
    "            g[a].append((b,0))\n",
    "        for c,d in blueEdges:   #从节点c走蓝色边到达节点d\n",
    "            g[c].append((d,1))\n",
    "        \n",
    "        ans=[inf]*n\n",
    "        visited=[[False]*2 for _ in range(n)]   #标记是否有从红色或蓝色的边到达该节点\n",
    "        queue=[(0,0),(0,1)] #假设存在一个哨兵起点，分别存在红色和蓝色的边到达节点0\n",
    "        #BFS\n",
    "        dis=0\n",
    "        while queue:\n",
    "            tmp=[]\n",
    "            while queue:\n",
    "                fa,fc=queue.pop()\n",
    "                visited[fa][fc]=True\n",
    "                ans[fa]=min(dis,ans[fa])\n",
    "                for (cur,cc) in g[fa]:\n",
    "                    if not visited[cur][cc] and cc!=fc:#\n",
    "                        tmp.append((cur,cc))\n",
    "            dis+=1\n",
    "            queue=tmp\n",
    "        for i in range(n):\n",
    "            if ans[i]==inf:\n",
    "                ans[i]=-1\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c=q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i]=d\n",
    "                vis.add((i,c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestAlternatingPaths(self, n, redEdges, blueEdges):\n",
    "\n",
    "        len_list=[400]*(n)\n",
    "        def iter_deq():\n",
    "            while deq:\n",
    "                tmp=deq.pop()\n",
    "                idx,flag,dist=tmp\n",
    "                if (idx,flag) in visited:\n",
    "                    continue\n",
    "                visited.add((idx,flag))\n",
    "                len_list[tmp[0]]=min(len_list[tmp[0]],dist)\n",
    "                dist +=1\n",
    "                ed=redEdges if tmp[1] else blueEdges\n",
    "                for i in [p for p in ed if p[0]==tmp[0]]:\n",
    "                    idx,tflag=i[1],not flag\n",
    "                    if (idx,tflag) in visited:\n",
    "                        continue\n",
    "                    deq.insert(0,(idx,tflag,dist))\n",
    "        deq=[]\n",
    "        deq.append((0,True,0))\n",
    "        deq.append((0,False,0))\n",
    "        visited = set()\n",
    "        iter_deq()\n",
    "        len_list=[p if p!=400 else -1 for p in len_list]\n",
    "        return len_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        re,be,rr={},{},[-1]*n\n",
    "        for e in redEdges:\n",
    "            if e[0] in re:re[e[0]]+=[e[1]]\n",
    "            else:re[e[0]]=[e[1]]\n",
    "        for e in blueEdges:\n",
    "            if e[0] in be:be[e[0]]+=[e[1]]\n",
    "            else:be[e[0]]=[e[1]]\n",
    "        q=collections.deque([('',[0])])\n",
    "        vr,vb=set(),set()\n",
    "        while q:\n",
    "            (c,p)=q.popleft()\n",
    "            if rr[p[-1]]==-1:rr[p[-1]]=len(p)-1\n",
    "            if c!='b':\n",
    "                if p[-1] in be:\n",
    "                    for i in be[p[-1]]:\n",
    "                        if i in vb:continue\n",
    "                        q.append(('b',p+[i]))\n",
    "                        vb.add(i)\n",
    "            if c!='r':\n",
    "                if p[-1] in re:\n",
    "                    for i in re[p[-1]]:\n",
    "                        if i in vr:continue\n",
    "                        q.append(('r',p+[i]))\n",
    "                        vr.add(i)\n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        # g是一个列表，g[i]是一个二元组或者二元列表，存放i的一个后续节点+边的颜色\n",
    "        g = [[]for _ in range(n)]\n",
    "        # 将红蓝边存入g\n",
    "        for x, y in redEdges:\n",
    "            g[x].append([y, 0])\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append([y, 1])\n",
    "        # 已经访问过的边\n",
    "        visited = [[0, 0], [0, 1]]\n",
    "        # que存放到当前节点i的所有边，这里是0，从0出发可以走蓝边也可以走红边，所以前面应该有两条边进来\n",
    "        # 后续的思路就是，que存放的是到当前点的前置边，考虑当前点的所有后继节点，颜色不同的就能走到下一个节点\n",
    "        que = [[0, 0], [0, 1]]\n",
    "        # 还没开始走，为0\n",
    "        step = 0\n",
    "        # 结果数组\n",
    "        dis = [-1]*n\n",
    "        while que:\n",
    "            # 将能走到当前节点的边都取出\n",
    "            tmp = que\n",
    "            que = []\n",
    "            for x, color in tmp:\n",
    "                # x点是可以走到的，若还是-1，则更新结果数组\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = step\n",
    "                # 把x能走下去的后继节点、颜色加入que，这条边不能之前走过\n",
    "                for nex, nex_color in g[x]:\n",
    "                    if nex_color != color and [nex, nex_color] not in visited:\n",
    "                        que.append([nex, nex_color])\n",
    "                        visited.append([nex, nex_color]) \n",
    "            # tmp所有都走完了\n",
    "            step += 1\n",
    "        return dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def shortestAlternatingPaths(\n",
    "\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "\n",
    "    ) -> List[int]:\n",
    "\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "\n",
    "        for i, j in redEdges:\n",
    "\n",
    "            g[0][i].append(j)\n",
    "\n",
    "        for i, j in blueEdges:\n",
    "\n",
    "            g[1][i].append(j)\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        vis = set()\n",
    "\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "\n",
    "        d = 0\n",
    "\n",
    "        while q:\n",
    "\n",
    "            for _ in range(len(q)):\n",
    "\n",
    "                i, c = q.popleft()\n",
    "\n",
    "                if ans[i] == -1:\n",
    "\n",
    "                    ans[i] = d\n",
    "\n",
    "                vis.add((i, c))\n",
    "\n",
    "                c ^= 1\n",
    "\n",
    "                for j in g[c][i]:\n",
    "\n",
    "                    if (j, c) not in vis:\n",
    "\n",
    "                        q.append((j, c))\n",
    "\n",
    "            d += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        # res1 = [-1] * n\n",
    "        # res2 = [-1] * n\n",
    "        # res = [res1, res2]\n",
    "        # vis = [set(),set()]\n",
    "        \n",
    "        # g = [[] for _ in range(n)]\n",
    "        # for x, y in redEdges:\n",
    "        #     g[x].append((y, 0))\n",
    "        # for x, y in blueEdges:\n",
    "        #     g[x].append((y, 1))\n",
    "\n",
    "        # for start_color in [0,1]:\n",
    "        #     q = [0]\n",
    "        #     cur_color = start_color\n",
    "        #     level = 0\n",
    "        #     while q:\n",
    "        #         level_size = len(q)\n",
    "        #         while level_size>0:\n",
    "        #             x = q.pop(0)\n",
    "        #             for y,c in g[x]:\n",
    "        #                 # print(x,y,c,cur_color)\n",
    "        #                 if c == cur_color:\n",
    "        #                     continue\n",
    "        #                 if (x,y,c) not in vis[start_color]: # not visited\n",
    "        #                     if res[start_color][y] == -1: # not visited\n",
    "        #                         res[start_color][y] = level + 1\n",
    "        #                     q.append(y)\n",
    "        #                     vis[start_color].add((x,y,c))\n",
    "        #             level_size -=1\n",
    "                \n",
    "        #         cur_color =  1-cur_color\n",
    "        #         level += 1\n",
    "        # merge_res = []\n",
    "        # for i in range(n):\n",
    "        #     if min(res[0][i],res[1][i]) == -1:\n",
    "        #         merge_res.append(max(res[0][i],res[1][i]))\n",
    "        #     else:\n",
    "        #         merge_res.append(min(res[0][i],res[1][i]))\n",
    "        # merge_res[0] = 0\n",
    "        # return merge_res\n",
    "        ans = [-1] * n\n",
    "        g = collections.defaultdict(list)\n",
    "        for i,j in redEdges:\n",
    "            g[i].append((j,0))\n",
    "        for i,j in blueEdges:\n",
    "            g[i].append((j,1))\n",
    "        q = collections.deque()\n",
    "        visited = [[0,0] for _ in range(n)]\n",
    "        q.append((0,0))\n",
    "        q.append((0,1))\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = collections.deque()\n",
    "            while tmp:\n",
    "                x, color = tmp.popleft()\n",
    "                ans[x] = min(ans[x],level) if ans[x] != -1 else level\n",
    "                for y, c in g[x]:\n",
    "                    if c == color:\n",
    "                        continue\n",
    "                    if visited[y][c] == 1:\n",
    "                        continue\n",
    "                    q.append((y,c))\n",
    "                    visited[y][c] = 1\n",
    "            level += 1\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        d = [[] for _ in range(n)]\n",
    "        for i,j in redEdges:\n",
    "            d[i].append((j,0))\n",
    "        for i,j in blueEdges:\n",
    "            if (j,0) in d[i]:\n",
    "                d[i].remove((j,0))\n",
    "                d[i].append((j,2))\n",
    "            else:d[i].append((j,1))\n",
    "\n",
    "        q = [(0,2)]\n",
    "        vis = set([(0,2)])\n",
    "        res = [-1]*n \n",
    "        l = 0\n",
    "        while q:\n",
    "            t = q\n",
    "            q = []\n",
    "\n",
    "            for i, w in t:\n",
    "\n",
    "                if res[i] == -1:\n",
    "                    res[i] = l\n",
    "                for r,j in enumerate(d[i]):\n",
    "                    if( j[1] == 2)and j not in vis:\n",
    "                        \n",
    "                        vis.add((j[0],1^w))\n",
    "                        q.append((j[0],1^w))\n",
    "                        d[i][r] = (j[0],w)\n",
    "                    elif w != j[1] and j not in vis:\n",
    "                        vis.add(j)\n",
    "                        q.append(j)\n",
    "            l += 1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        answer = [-1] * n\n",
    "        answer[0] = 0\n",
    "        # from collections import defaultdict\n",
    "        graph = {i: {1: [], 2: []} for i in range(n)} ### 1: red, 2: blue\n",
    "\n",
    "        for rededge in redEdges:\n",
    "            graph[rededge[0]][1].append(rededge[1])\n",
    "        \n",
    "        for blueedge in blueEdges:\n",
    "            graph[blueedge[0]][2].append(blueedge[1])   \n",
    "        \n",
    "        colors = [0] * n #### [0,1,2,3], 1:最近一条边是red， 2:最近一条边是blue， 3:red、blue均可，0: 未到达\n",
    "        colors[0] = 3\n",
    "        queue = [(0, 1, 0), (0, 2, 0)] #### (node, color, length)\n",
    "        # queue = [(0, 0)] #### (node, length)\n",
    "        while len(queue):\n",
    "            node, color, l = queue.pop()\n",
    "            op_color = 3 - color\n",
    "            for neighbor in graph[node][op_color]:\n",
    "                if colors[neighbor] == 0:\n",
    "                    colors[neighbor] = op_color\n",
    "                    answer[neighbor] = l + 1\n",
    "                    queue.insert(0, (neighbor, op_color, l+1))\n",
    "                elif colors[neighbor] == color:\n",
    "                    colors[neighbor] = 3\n",
    "                    queue.insert(0, (neighbor, op_color, l+1))\n",
    "\n",
    "\n",
    "\n",
    "        return answer\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        res = [float('inf') for _ in range(n)] #float('inf') is the custom way of representing largest numeber in python\n",
    "        res[0] = 0 # initialize diatance\n",
    "        queue = deque()\n",
    "        # queue: (current_node, current_length, color)\n",
    "        queue.append((0, 0, \"R\")) # initial node can be both color\n",
    "        queue.append((0, 0, \"B\"))\n",
    "        # visited: (end_node, color)\n",
    "        visited = set()\n",
    "        visited.add((0,\"R\"))\n",
    "        visited.add((0,\"B\"))\n",
    "        while queue:\n",
    "            cur_node, cur_length, color = queue.popleft()\n",
    "            if color == \"B\":\n",
    "                for start,end in blueEdges:\n",
    "                    if start == cur_node and (end, \"R\") not in visited:\n",
    "                        res[end] = min(cur_length + 1, res[end]) # update the shortest distance\n",
    "                        # update visited\n",
    "                        visited.add((end, \"R\"))\n",
    "                        # update queue\n",
    "                        queue.append( (end, cur_length + 1, \"R\"))\n",
    "            elif color == \"R\":\n",
    "                for start, end in redEdges:\n",
    "                    if start == cur_node and (end, \"B\") not in visited:\n",
    "                        res[end] = min(cur_length + 1, res[end])\n",
    "                        visited.add((end, \"B\"))\n",
    "                        queue.append((end, cur_length + 1, \"B\"))\n",
    "        # modify all values that are flaot('inf')\n",
    "        for i in range(len(res)):\n",
    "            if(res[i] == float('inf')):\n",
    "                res[i] = -1\n",
    "        return res\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shortestAlternatingPaths(self, n, redEdges, blueEdges):\n",
    "\n",
    "        len_list=[0]+[400]*(n-1)\n",
    "        def iter_deq():\n",
    "            while deq:\n",
    "                tmp=deq.pop()\n",
    "                idx,flag,dist=tmp\n",
    "                if (idx,flag) in visited:\n",
    "                    continue\n",
    "                visited.add((idx,flag))\n",
    "                len_list[tmp[0]]=min(len_list[tmp[0]],dist)\n",
    "                dist +=1\n",
    "                ed=redEdges if tmp[1] else blueEdges\n",
    "                for i in [p for p in ed if p[0]==tmp[0]]:\n",
    "                    idx,tflag=i[1],not flag\n",
    "                    if (idx,tflag) in visited:\n",
    "                        continue\n",
    "                    deq.insert(0,(idx,tflag,dist))\n",
    "        deq=[]\n",
    "        deq.append((0,True,0))\n",
    "        visited = set()\n",
    "        iter_deq()\n",
    "        deq=[]\n",
    "        deq.append((0,False,0))\n",
    "        visited = set()\n",
    "        iter_deq()\n",
    "        len_list=[p if p!=400 else -1 for p in len_list]\n",
    "        return len_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        #0-red, 1-blue\n",
    "        path = [defaultdict(list), defaultdict(list)]\n",
    "        for e in redEdges:\n",
    "            path[0][e[0]].append(e[1])\n",
    "        for e in blueEdges:\n",
    "            path[1][e[0]].append(e[1])\n",
    "        \n",
    "        seen = set()\n",
    "        seen.add((0,0))\n",
    "        seen.add((0,1))\n",
    "        queue = [(0,0),(0,1)]\n",
    "        ans = [-1]*n\n",
    "        depth = 0\n",
    "\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur, c = queue.pop(0)\n",
    "                if ans[cur] == -1:\n",
    "                    ans[cur] = depth\n",
    "\n",
    "                c ^= 1\n",
    "                for neighbor in path[c][cur]:\n",
    "                    if (neighbor,c) not in seen:\n",
    "                        seen.add((neighbor,c))\n",
    "                        queue.append((neighbor,c))\n",
    "\n",
    "\n",
    "            depth += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        #dijkstra #todo\n",
    "        \"\"\" dct_red = defaultdict(dict)\n",
    "        dct_blue = defaultdict(dict)\n",
    "        for u,v in redEdges:\n",
    "            dct_red[u][v] = w\n",
    "        for u,v in blueEdges:\n",
    "            dct_blue[u][v] = w\n",
    "        dist = [inf]*n\n",
    "        dist[0] = 0\n",
    "        stack = [[0,0]]\n",
    "        while stack:\n",
    "            d,i = heappop(stack)\n",
    "            if d > dist[i]:\n",
    "                continue \"\"\"\n",
    "\n",
    "        #bfs\n",
    "        q = deque()\n",
    "        cnt = 0\n",
    "        answer = [-1] * n\n",
    "        red_answer = [-1] * n\n",
    "        blue_answer = [-1] * n\n",
    "        red_visited = [False]* n\n",
    "        #print(red_visited[1])\n",
    "        blue_visited = [False]* n\n",
    "        red_dct = defaultdict(list)\n",
    "        blue_dct = defaultdict(list)\n",
    "        for u,v in redEdges:\n",
    "            red_dct[(0,u)].append((0,v))#0 is red\n",
    "        for u,v in blueEdges:\n",
    "            blue_dct[(1,u)].append((1,v))#1 is blue\n",
    "        q.append((0,0))\n",
    "        red_visited[0] = True\n",
    "        red_answer[0] = 0\n",
    "        q.append((1,0))\n",
    "        blue_visited[0] = True\n",
    "        blue_answer[0] = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            cnt += 1\n",
    "            for k in range(size):\n",
    "                item = q.popleft()\n",
    "                if item[0] == 0:\n",
    "                    for i in blue_dct[(1,item[1])]:\n",
    "                        if blue_visited[i[1]] == False:\n",
    "                            #cnt += 1\n",
    "                            blue_answer[i[1]] = cnt\n",
    "                            q.append(i)\n",
    "                            blue_visited[i[1]] = True\n",
    "                elif item[0] == 1:\n",
    "                    for i in red_dct[(0,item[1])]:\n",
    "                        if not red_visited[i[1]]:\n",
    "                            #cnt += 1\n",
    "                            red_answer[i[1]] = cnt\n",
    "                            q.append(i)\n",
    "                            red_visited[i[1]] = True\n",
    "            \n",
    "        for i in range(n):\n",
    "            if red_answer[i] == -1 and blue_answer[i] == -1:\n",
    "                answer[i] = -1\n",
    "            elif red_answer[i] == -1:\n",
    "                answer[i] = blue_answer[i]\n",
    "            elif blue_answer[i] == -1:\n",
    "                answer[i] = red_answer[i]\n",
    "            else:\n",
    "                answer[i] = min(red_answer[i],blue_answer[i])\n",
    "        return answer\n",
    "            \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "\n",
    "        res = [-1] * n\n",
    "        visted = set()\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        level = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, color = q.pop(0)\n",
    "                if res[i] == -1:\n",
    "                    res[i] = level\n",
    "                visted.add((i, color))\n",
    "                color ^= 1\n",
    "                for j in g[color][i]:\n",
    "                    if (j, color) not in visted:\n",
    "                        q.append((j, color))\n",
    "            level += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestAlternatingPaths(\n",
    "#         self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "#     ) -> List[int]:\n",
    "#         # g[color][i]\n",
    "#         g = [defaultdict(list), defaultdict(list)]\n",
    "#         for i, j in redEdges:\n",
    "#             # 0 代表红色\n",
    "#             g[0][i].append(j)\n",
    "\n",
    "#         for i, j in blueEdges:\n",
    "#             # 1 代表蓝色\n",
    "#             g[1][i].append(j)\n",
    "\n",
    "#         # [i, color]\n",
    "#         visited = set()\n",
    "#         res = [-1] * n\n",
    "#         level = 0 # 层数\n",
    "#         q = [[0, 0], [0, 1]]  # 红蓝都从0开始\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i, color = q.pop(0)\n",
    "#                 if res[i] == -1:\n",
    "#                     res[i] = level\n",
    "#                 visited.add((i, color))\n",
    "#                 # 红蓝交替\n",
    "#                 color ^= 1\n",
    "#                 for j in g[color][i]:\n",
    "#                     if (j, color) not in visited:\n",
    "#                         q.append([j, color])\n",
    "#             level += 1\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        rd, bd, md = defaultdict(list), defaultdict(list), defaultdict(lambda:float('inf'))\n",
    "        for u, v in redEdges: rd[u].append(v)\n",
    "        for u, v in blueEdges: bd[u].append(v)\n",
    "\n",
    "        qu = [[0, 1, 0], [0, -1, 0]]\n",
    "        r, b = 1, -1\n",
    "        v = set([(0, 1), (0, -1)])\n",
    "\n",
    "        while qu:\n",
    "            pos, c, sp = qu.pop(0)\n",
    "            md[pos] = min(md[pos],sp)\n",
    "            d = rd if c==1 else bd\n",
    "            for pn in d[pos]:\n",
    "                if (pn, -c) not in v:\n",
    "                    qu.append([pn, -c, sp+1])\n",
    "                    v.add((pn, -c))\n",
    "        \n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if md[i] != float('inf'):\n",
    "                res.append(md[i])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for edge in redEdges:\n",
    "            g[edge[0]].append((edge[1], 0))\n",
    "        for edge in blueEdges:\n",
    "            g[edge[0]].append((edge[1], 1))\n",
    "        \n",
    "        q = [(0,0),(0,1)]\n",
    "        vis = {(0,0),(0,1)}\n",
    "        dis = [-1] * n\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            level +=1\n",
    "        return dis\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        dis = [-1] * n\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            level += 1\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n , redEdges , blueEdges ) :\n",
    "        red_path = defaultdict(list)\n",
    "        blue_path = defaultdict(list)\n",
    "        \n",
    "        for s, e in redEdges:\n",
    "            red_path[s].append(e)\n",
    "            \n",
    "        for s, e in blueEdges:\n",
    "            blue_path[s].append(e)\n",
    "        \n",
    "        q = deque([[0, 0, 0]])\n",
    "        ans = [float('inf')] * n\n",
    "        ans[0] = 0\n",
    "        vis_red = [False] * n\n",
    "        vis_blue = [False] * n\n",
    "        \n",
    "        while q:\n",
    "            node, step, per = q.popleft()\n",
    "            if per != 1:\n",
    "                for next_node in red_path[node]:\n",
    "                    if not vis_red[next_node]:\n",
    "                        q.append((next_node, step + 1, 1))\n",
    "                        ans[next_node] = min(ans[next_node], step + 1)\n",
    "                        vis_red[next_node] = True\n",
    "            if per != 2:\n",
    "                for next_node in blue_path[node]:\n",
    "                    if not vis_blue[next_node]:\n",
    "                        q.append((next_node, step + 1, 2))\n",
    "                        ans[next_node] = min(ans[next_node], step + 1)\n",
    "                        vis_blue[next_node] = True\n",
    "                \n",
    "        for index, item in enumerate(ans):\n",
    "            if item == float('inf'):\n",
    "                ans[index] = -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        dis = [-1] * n\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            level += 1\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:\n",
    "        red, blue = 0, 1\n",
    "        graph = [[[], []] for _ in range(n)]\n",
    "        for i, j in red_edges:\n",
    "            graph[i][red].append(j)\n",
    "        for i, j in blue_edges:\n",
    "            graph[i][blue].append(j)\n",
    "        res =[[0, 0]] + [[n * 2, n * 2] for _ in range(n-1)]\n",
    "        bfs = deque([(0, red), (0, blue)])\n",
    "        while bfs:\n",
    "            node, color = bfs.popleft()\n",
    "            for nei in graph[node][color]:\n",
    "                if res[nei][color] == n * 2:\n",
    "                    res[nei][color] = res[node][1 - color] + 1\n",
    "                    bfs.append((nei, 1 - color))\n",
    "        return [x if x < n * 2 else -1 for x in map(min, res)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "\t\t\t\t# 第0个点有两种可能\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1  # 取反\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1 # 遍历的层数\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        edges = []\n",
    "        for e in redEdges:\n",
    "            edges.append([e[0],e[1],0])\n",
    "        for e in blueEdges:\n",
    "            edges.append([e[0],e[1],1]) \n",
    "        resr = [10000000000000]*n\n",
    "        resb = [10000000000000]*n\n",
    "        resr[0] = 0\n",
    "        resb[0] = 0\n",
    "        for i in range(n-1):\n",
    "            for e in edges:\n",
    "                if e[2] == 0:\n",
    "                    if resb[e[0]]!=10000000000000 and resr[e[1]]>resb[e[0]]+1:\n",
    "                        resr[e[1]] = resb[e[0]]+1\n",
    "                elif e[2] == 1:\n",
    "                    if resr[e[0]]!=10000000000000 and resb[e[1]]>resr[e[0]]+1:\n",
    "                        resb[e[1]] = resr[e[0]]+1\n",
    "\n",
    "                    \n",
    "\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if resr[i]!=10000000000000 or resb[i]!=10000000000000:\n",
    "                res.append(min(resr[i],resb[i]))\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        p = []\n",
    "        p.append(redEdges)\n",
    "        p.append(blueEdges)\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        m = 0\n",
    "        l = 0\n",
    "        t1 = [0] \n",
    "        t2 = [0]\n",
    "        while len(t1) or len(t2):\n",
    "            t = []\n",
    "            pr1 = []\n",
    "            pr2 = []\n",
    "            m = m % 2\n",
    "            for e in t1:\n",
    "                for i in p[m]:\n",
    "                    if i[0] == e:\n",
    "                        if ans[i[1]] == -1:\n",
    "                            ans[i[1]] = l + 1\n",
    "                        if t.count(i[1])==0:    \n",
    "                            t.append(i[1])    \n",
    "                        pr1.append(i)\n",
    "            for i in pr1:\n",
    "                p[m].remove(i)             \n",
    "            t1 = t\n",
    "            m = m + 1\n",
    "\n",
    "            t = []\n",
    "            m = m % 2\n",
    "            for e in t2:\n",
    "                for i in p[m]:\n",
    "                    if i[0] == e: \n",
    "                        if ans[i[1]] == -1:\n",
    "                            ans[i[1]] = l + 1\n",
    "                        if t.count(i[1])==0:    \n",
    "                            t.append(i[1])\n",
    "                        pr2.append(i)\n",
    "            t2 = t\n",
    "            l = l + 1\n",
    "            for i in pr2:\n",
    "                p[m].remove(i)\n",
    "   \n",
    "\n",
    "\n",
    "        ans[0] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def build_graph(edges):\n",
    "    graph = collections.defaultdict(set)\n",
    "    for edge in edges:\n",
    "        graph[edge[0]].add(edge[1])\n",
    "    return graph\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:\n",
    "        red_graph = build_graph(red_edges)\n",
    "        blue_graph = build_graph(blue_edges)\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        # 先红色边的情况\n",
    "        visited_red = {0}\n",
    "        visited_blue = set()\n",
    "        queue = collections.deque([0])\n",
    "        step = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                n1 = queue.popleft()\n",
    "                if ans[n1] == -1 or ans[n1] > step:\n",
    "                    ans[n1] = step\n",
    "                if step % 2 == 0:\n",
    "                    for n2 in red_graph[n1]:\n",
    "                        if n2 not in visited_blue:\n",
    "                            visited_blue.add(n2)\n",
    "                            queue.append(n2)\n",
    "                else:\n",
    "                    for n2 in blue_graph[n1]:\n",
    "                        if n2 not in visited_red:\n",
    "                            visited_red.add(n2)\n",
    "                            queue.append(n2)\n",
    "            step += 1\n",
    "\n",
    "        # 先蓝色边的情况\n",
    "        visited_red = set()\n",
    "        visited_blue = {0}\n",
    "        queue = collections.deque([0])\n",
    "        step = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                n1 = queue.popleft()\n",
    "                if ans[n1] == -1 or ans[n1] > step:\n",
    "                    ans[n1] = step\n",
    "                if step % 2 == 0:\n",
    "                    for n2 in blue_graph[n1]:\n",
    "                        if n2 not in visited_red:\n",
    "                            visited_red.add(n2)\n",
    "                            queue.append(n2)\n",
    "                else:\n",
    "                    for n2 in red_graph[n1]:\n",
    "                        if n2 not in visited_blue:\n",
    "                            visited_blue.add(n2)\n",
    "                            queue.append(n2)\n",
    "            step += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in redEdges:\n",
    "            graph[a].append((b, 0))\n",
    "        for u, v in blueEdges:\n",
    "            graph[u].append((v, 1))\n",
    "        \n",
    "        que = collections.deque([(0, 0), (0, 1)])\n",
    "        dist = [-1] * n\n",
    "        level = 0\n",
    "        v = [[False, False] for _ in range(n)]\n",
    "        v[0][0], v[0][1] = True, True\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                node, color = que.popleft()\n",
    "                if dist[node] == -1:\n",
    "                    dist[node] = level\n",
    "                for nex, nex_color in graph[node]:\n",
    "                    if v[nex][nex_color]:\n",
    "                        continue\n",
    "                    if nex_color != color:\n",
    "                        que.append((nex, nex_color))\n",
    "                        v[nex][nex_color] = True\n",
    "            level += 1\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph =[[[] for _ in range(n)] for _ in range(2)]\n",
    "        for edge in redEdges:\n",
    "            graph[1][edge[0]].append(edge[1])\n",
    "        for edge in blueEdges:\n",
    "            graph[0][edge[0]].append(edge[1])    \n",
    "        visited = set()     \n",
    "        res =[-1]*n\n",
    "        pq = Queue()      \n",
    "        pq.put((0,0))\n",
    "        pq.put((0,1))                  \n",
    "        d = 0\n",
    "        while not pq.empty():\n",
    "            for _ in range(pq.qsize()):\n",
    "                node,color = pq.get()\n",
    "                if res[node] == -1: res[node] = d\n",
    "                visited.add((node,color))\n",
    "                color^=1\n",
    "                for j in graph[color][node]:\n",
    "                    if (j,color) not in visited:\n",
    "                        pq.put((j,color))\n",
    "            d+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for s, t in redEdges:\n",
    "            g[s].append((t, 0))\n",
    "        for s, t in blueEdges:\n",
    "            g[s].append((t, 1))\n",
    "        dis = [-1] * n\n",
    "        # 由0到0开始,0到0的颜色两种均可加上不会对结构有影响\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        level = 0\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                node, color = q.pop(0)\n",
    "                if dis[node] == -1:\n",
    "                    dis[node] = level\n",
    "                for p in g[node]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        q.append(p)\n",
    "                        vis.add(p)\n",
    "            level += 1\n",
    "        return dis\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #bfs，可以保证达到每个节点时路径是最短的。\n",
    "        #dist[i][0],表示从节点0到节点i为 红蓝红... 类型,最后一条边为红\n",
    "        #dist[i][1],表示从节点0到节点i为 蓝红蓝... 类型\n",
    "        #dist[i][0] = -1,表示该路径不可达\n",
    "        #首先，算出从0开始，到每一个节点的两条路径的最短距离\n",
    "        #再在这两条路径中选择较小的那一个\n",
    "\n",
    "        red_path = [set() for _ in range(n)] #使用set加快查找\n",
    "        blue_path = [set() for _ in range(n)]\n",
    "        dist = [[-1,-1] for _ in range(n)]\n",
    "        dist[0] = [0,0]\n",
    "        step = 0\n",
    "        now_red = [0]\n",
    "        now_blue = [0]\n",
    "        for start,end in redEdges:\n",
    "            red_path[start].add(end)\n",
    "        for start,end in blueEdges:\n",
    "            blue_path[start].add(end)\n",
    "\n",
    "        #分别找到以红边开始和蓝边开始的两条路径\n",
    "        while now_red or now_blue:\n",
    "            new_red = []\n",
    "            new_blue = []\n",
    "            step += 1\n",
    "            if now_blue:\n",
    "                for node in now_blue:\n",
    "                    for next_node in red_path[node]:\n",
    "                        if dist[next_node][0] == -1:\n",
    "                            dist[next_node][0] = step\n",
    "                            new_red.append(next_node)\n",
    "            if now_red:\n",
    "                for node in now_red:\n",
    "                    for next_node in blue_path[node]:\n",
    "                        if dist[next_node][1] == -1:\n",
    "                            dist[next_node][1] = step\n",
    "                            new_blue.append(next_node)\n",
    "            now_red,now_blue = new_red,new_blue\n",
    "        \n",
    "        res = []\n",
    "        for x,y in dist:\n",
    "            if x == y == -1:\n",
    "                res.append(-1)\n",
    "            elif x == -1:\n",
    "                res.append(y)\n",
    "            elif y == -1:\n",
    "                res.append(x)\n",
    "            else:\n",
    "                res.append(min(x,y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        INF=10**100\n",
    "        rch=[[] for _ in range(n)]\n",
    "        bch=[[] for _ in range(n)]\n",
    "        for u,v in redEdges:\n",
    "            rch[u].append(v)\n",
    "        for u,v in blueEdges:\n",
    "            bch[u].append(v)\n",
    "        rres=[INF]*n;bres=[INF]*n\n",
    "        rres[0]=0;bres[0]=0\n",
    "        f=1\n",
    "        while(f):\n",
    "            f-=1\n",
    "            for i in range(n):\n",
    "                for c in rch[i]:\n",
    "                    if bres[i]+1<rres[c]:\n",
    "                        f=1\n",
    "                        rres[c]=bres[i]+1\n",
    "                for c in bch[i]:\n",
    "                    if rres[i]+1<bres[c]:\n",
    "                        f=1\n",
    "                        bres[c]=rres[i]+1\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            t=min(bres[i],rres[i])\n",
    "            res.append(t if t!=INF else -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "        visited = {(0, 0), (0, 1)}\n",
    "        p = [(0, 0), (0, 1)]\n",
    "        lujin = [-1]*n\n",
    "        lev = 0\n",
    "        while p:\n",
    "            temp = []\n",
    "            for x, color in p:\n",
    "                if lujin[x] == -1:\n",
    "                    lujin[x] = lev\n",
    "                for gg in g[x]:\n",
    "                    if gg[1] == color or gg in visited:\n",
    "                        continue\n",
    "                    visited.add(gg)\n",
    "                    temp.append(gg)\n",
    "            p = temp\n",
    "            lev += 1\n",
    "        return lujin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        BFS第一次找到的一定是最短路径 注意再加入时 观察路径的颜色和之前加入的颜色要相反\n",
    "        \"\"\"\n",
    "        rs = [-1 for _ in range(n)]\n",
    "        rs[0] = 0\n",
    "        g = defaultdict(list)  # 构建图\n",
    "        for u, v in redEdges:\n",
    "            g[u].append((v, -1))  # -1代表红色\n",
    "        for u, v in blueEdges:\n",
    "            g[u].append((v, 1))  # 1代表蓝色\n",
    "        queue = deque([(0, 0)]) #0代表通用\n",
    "        seen = set([])\n",
    "        steps = 1\n",
    "        cnt = n-1\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                u, c1 = queue.popleft()\n",
    "                neiborhoods = g[u]\n",
    "                for v, c2 in neiborhoods:\n",
    "                    if c1 * c2 <= 0 and (v, c2) not in seen:\n",
    "                        seen.add((v, c2))\n",
    "                        if rs[v] == -1:\n",
    "                            rs[v] = steps\n",
    "                            cnt -= 1\n",
    "                        queue.append((v, c2))\n",
    "            if cnt == 0:\n",
    "                break\n",
    "            steps += 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        dis= [-1]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in redEdges:\n",
    "            g[x].append((y,0))\n",
    "        for x,y in blueEdges:\n",
    "            g[x].append((y,1))\n",
    "        vis = {(0,0),(0,1)}\n",
    "        q = [(0,0),(0,1)]\n",
    "        cnt = 0 \n",
    "        # bfs\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x,color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = cnt\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            cnt+=1\n",
    "        return dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        dis = [-1] * n\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        q = [(0, 0), (0, 1)] # 加入起始点两种不同的颜色\n",
    "        level = 0\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                x, color = q[0]\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    # 红蓝交替所以需要颜色不一样\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "                q.pop(0)\n",
    "            level += 1\n",
    "        return dis\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        bluedist = [float('inf')]*n\n",
    "        reddist = [float('inf')]*n\n",
    "        graph = defaultdict(lambda: [])\n",
    "        bluee = defaultdict(lambda: [])\n",
    "        reddist[0] = 0\n",
    "        bluedist[0] = 0\n",
    "        for a, b in redEdges:\n",
    "            graph[a].append((b, 0))\n",
    "\n",
    "        for a, b in blueEdges:\n",
    "            graph[a].append((b, 1))\n",
    "\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        tmp = []\n",
    "        visited = defaultdict(lambda: False)\n",
    "        visited[(0, 0)] = True\n",
    "        visited[(0, 1)] = True\n",
    "        ret = [-1]*n\n",
    "        steps = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for a, b in tmp:\n",
    "                if ret[a] == -1:\n",
    "                    ret[a] = steps\n",
    "                for na, nb in graph[a]:\n",
    "                    if nb != b and not visited[(na, nb)]:\n",
    "                        q.append((na, nb))\n",
    "                        visited[(na, nb)] = True\n",
    "            steps += 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "\n",
    "        visited = set()\n",
    "        res = [-1] * n\n",
    "        level = 0\n",
    "        q = [[0, 0], [0, 1]]\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, color = q.pop(0)\n",
    "                if res[i] == -1:\n",
    "                    res[i] = level\n",
    "                visited.add((i, color))\n",
    "                color ^= 1\n",
    "                for j in g[color][i]:\n",
    "                    if (j, color) not in visited:\n",
    "                        q.append([j, color])\n",
    "            level += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestAlternatingPaths(\n",
    "#         self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "#     ) -> List[int]:\n",
    "#         # g[color][i]\n",
    "#         g = [defaultdict(list), defaultdict(list)]\n",
    "#         for i, j in redEdges:\n",
    "#             # 0 代表红色\n",
    "#             g[0][i].append(j)\n",
    "\n",
    "#         for i, j in blueEdges:\n",
    "#             # 1 代表蓝色\n",
    "#             g[1][i].append(j)\n",
    "\n",
    "#         # [i, color]\n",
    "#         visited = set()\n",
    "#         res = [-1] * n\n",
    "#         level = 0 # 层数\n",
    "#         q = [[0, 0], [0, 1]]  # 红蓝都从0开始\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i, color = q.pop(0)\n",
    "#                 if res[i] == -1:\n",
    "#                     res[i] = level\n",
    "#                 visited.add((i, color))\n",
    "#                 # 红蓝交替\n",
    "#                 color ^= 1\n",
    "#                 for j in g[color][i]:\n",
    "#                     if (j, color) not in visited:\n",
    "#                         q.append([j, color])\n",
    "#             level += 1\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        answer = [-1] * n \n",
    "        g = collections.defaultdict(list)\n",
    "        for i,j in redEdges:\n",
    "            g[i].append((j,0))\n",
    "        for i,j in blueEdges:\n",
    "            g[i].append((j,1))\n",
    "        q = collections.deque([(0,0),(0,1)])\n",
    "        answer[0] = 0\n",
    "        level = 1\n",
    "        visited = set([(0,0),(0,1)])\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = collections.deque()\n",
    "            while tmp:\n",
    "                x,x_c = tmp.popleft()\n",
    "                for y,y_c in g[x]:\n",
    "                    if y_c != x_c and not (y,y_c) in visited:\n",
    "                        visited.add((y,y_c))\n",
    "                        q.append((y,y_c))\n",
    "                        if answer[y] == -1:\n",
    "                            answer[y] = level\n",
    "            level += 1\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        res = [-1 for _ in range(n)]\n",
    "        redGraph = defaultdict(list)\n",
    "        for edge in redEdges:\n",
    "            redGraph[edge[0]].append(edge[1])\n",
    "        blueGraph = defaultdict(list)\n",
    "        for edge in blueEdges:\n",
    "            blueGraph[edge[0]].append(edge[1])\n",
    "\n",
    "        # self.traverse(0, 0, redGraph, blueGraph, True, set(), res)\n",
    "        nextNodes = [(0, 0, True)]\n",
    "        visited = set()\n",
    "        while nextNodes:\n",
    "            node, step, useRed = nextNodes.pop(0)\n",
    "            if (useRed, node) in visited:\n",
    "                continue\n",
    "            visited.add((useRed, node))\n",
    "            if res[node] == -1 or step < res[node]:\n",
    "                res[node] = step\n",
    "            graph = blueGraph\n",
    "            if useRed:\n",
    "                graph = redGraph\n",
    "            for nextNode in graph[node]:\n",
    "                nextNodes.append((nextNode, step + 1, not useRed))\n",
    "        \n",
    "        nextNodes = [(0, 0, False)]\n",
    "        visited = set()\n",
    "        while nextNodes:\n",
    "            node, step, useRed = nextNodes.pop(0)\n",
    "            if (useRed, node) in visited:\n",
    "                continue\n",
    "            visited.add((useRed, node))\n",
    "            if res[node] == -1 or step < res[node]:\n",
    "                res[node] = step\n",
    "            graph = blueGraph\n",
    "            if useRed:\n",
    "                graph = redGraph\n",
    "            for nextNode in graph[node]:\n",
    "                nextNodes.append((nextNode, step + 1, not useRed))\n",
    "    \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * n\n",
    "        searched = defaultdict(int)\n",
    "        que = deque([0])\n",
    "        step = -1\n",
    "        #从红色边开始搜索\n",
    "        while que:\n",
    "            step+=1\n",
    "            l = len(que)\n",
    "            for _ in range(l):\n",
    "                cur = que.popleft()\n",
    "                ans[cur] = min(step,ans[cur]) if ans[cur] != -1 else step\n",
    "                searched[cur]+=1\n",
    "                if step % 2 == 0:\n",
    "                    for tmp,nxt in redEdges:\n",
    "                        if tmp == cur and searched[nxt]<n:\n",
    "                            que.append(nxt)\n",
    "                else:\n",
    "                    for tmp,nxt in blueEdges :\n",
    "                        if tmp == cur and searched[nxt]<n:\n",
    "                            que.append(nxt)\n",
    "        searched = defaultdict(int)\n",
    "        que = deque([0])\n",
    "        step = -1\n",
    "        #从l色边开始搜索\n",
    "        while que:\n",
    "            step+=1\n",
    "            l = len(que)\n",
    "            for _ in range(l):\n",
    "                cur = que.popleft()\n",
    "                ans[cur] = min(step,ans[cur]) if ans[cur] != -1 else step\n",
    "                searched[cur]+=1\n",
    "                if step % 2 == 0:\n",
    "                    for tmp,nxt in blueEdges:\n",
    "                        if tmp == cur and searched[nxt]<n:\n",
    "                            que.append(nxt)\n",
    "                else:\n",
    "                    for tmp,nxt in redEdges :\n",
    "                        if tmp == cur and searched[nxt]<n:\n",
    "                            que.append(nxt)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "从零开始广度优先搜索 如果有,分别从红色开始,蓝色开始\n",
    "搜索的同一层颜色相同,相邻层的颜色不同\n",
    "搜索过程中第一次出现的节点答案对当前层数\n",
    "\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for r in redEdges:\n",
    "            graph[r[0]].append((r[1],'r'))\n",
    "        for b in blueEdges:\n",
    "            graph[b[0]].append((b[1],'b'))\n",
    "\n",
    "        print(graph)\n",
    "        is_visited = set()\n",
    "        now_q = [(0,'r'),(0,'b')]\n",
    "        level = 0\n",
    "        ans = [-1]*n\n",
    "        while now_q:\n",
    "            next_q = []\n",
    "            for x,color in now_q:\n",
    "                is_visited.add((x,color))\n",
    "                if ans[x] == -1:\n",
    "                    ans[x]=level\n",
    "                for nx,nc in graph[x]:\n",
    "                    if (nx,nc) not in is_visited and nc!=color:\n",
    "                        next_q.append((nx,nc))\n",
    "\n",
    "            now_q=next_q\n",
    "            level+=1\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in redEdges:\n",
    "            g[x].append((y,0))\n",
    "        for x,y in blueEdges:\n",
    "            g[x].append((y,1))\n",
    "        \n",
    "        dist = [-1 for _ in range(n)]\n",
    "        dist[0] = 0\n",
    "        vis = {(0,0), (0,1)}\n",
    "        pairQ = [(0,0), (0,1)]\n",
    "        step = 0\n",
    "        while len(pairQ) > 0:\n",
    "            k = len(pairQ)\n",
    "            while k>0:\n",
    "                x, color = pairQ.pop(0)\n",
    "                if dist[x]==-1:\n",
    "                    dist[x]=step\n",
    "                for pair in g[x]:\n",
    "                    if color!=pair[1] and pair not in vis:\n",
    "                        vis.add(pair)\n",
    "                        pairQ.append(pair)\n",
    "                k -= 1\n",
    "            step += 1\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        gr, gb = defaultdict(list), defaultdict(list)\n",
    "        for u, v in redEdges:\n",
    "            gr[u].append(v)\n",
    "        for u, v in blueEdges:\n",
    "            gb[u].append(v)\n",
    "\n",
    "        ans = [-1] * n\n",
    "        q = [(0, 0),(0, 1)]\n",
    "        d = 0\n",
    "        s = set()\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = [] \n",
    "            for x, color in tmp:\n",
    "                ans[x] = d if ans[x] == -1 else min(ans[x], d)\n",
    "                s.add((x,color))\n",
    "                if color == 0:\n",
    "                    for y in gb[x]:\n",
    "                        if (y, 1) not in s:\n",
    "                            q.append((y, 1))\n",
    "                if color == 1:\n",
    "                    for y in gr[x]:\n",
    "                        if (y, 0) not in s:\n",
    "                            q.append((y, 0))\n",
    "            d += 1       \n",
    "        return ans\n",
    "            \n",
    "                       \n",
    "                       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        next:List[List[int]] = []\n",
    "        for i in range(2):\n",
    "            _t = []\n",
    "            for i in range(n):\n",
    "                _t.append([])\n",
    "            next.append(_t)\n",
    "        \n",
    "        for edge in redEdges:\n",
    "            next[0][edge[0]].append(edge[1])\n",
    "        for edge in blueEdges:\n",
    "            next[1][edge[0]].append(edge[1])\n",
    "        import sys\n",
    "        dist = [[sys.maxsize]*n,[sys.maxsize]*n]\n",
    "        dist[0][0] = 0\n",
    "        dist[1][0] = 0\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q.put([0,0])\n",
    "        q.put([0,1])\n",
    "        while not q.empty():\n",
    "            pair = q.get()\n",
    "            f = pair[0]\n",
    "            tp = pair[1]\n",
    "            for t in next[1-tp][f]:\n",
    "                if dist[1-tp][t] != sys.maxsize:\n",
    "                    continue\n",
    "                dist[1-tp][t] = dist[tp][f] + 1\n",
    "                q.put([t,1-tp])\n",
    "        res = [sys.maxsize]*n\n",
    "        for i in range(n):\n",
    "            res[i] = min(dist[0][i],dist[1][i])\n",
    "            if res[i] == sys.maxsize:\n",
    "                res[i] = -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # red =[[] for i in range(n)]\n",
    "        # for edge in redEdges:\n",
    "        #     red[edge[0]].append((edge[1]))\n",
    "        # blue =[[] for i in range(n)]\n",
    "        # for edge in blueEdges:\n",
    "        #     blue[edge[0]].append((edge[1]))\n",
    "        \n",
    "       \n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        dis = [-1] * n\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        q = [(0, 0), (0, 1)]\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, color in tmp:\n",
    "                if dis[x] == -1:\n",
    "                    dis[x] = level\n",
    "                for p in g[x]:\n",
    "                    if p[1] != color and p not in vis:\n",
    "                        vis.add(p)\n",
    "                        q.append(p)\n",
    "            level += 1\n",
    "        return dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        bluedist = [float('inf')]*n\n",
    "        reddist = [float('inf')]*n\n",
    "        rede = defaultdict(lambda: [])\n",
    "        bluee = defaultdict(lambda: [])\n",
    "        reddist[0] = 0\n",
    "        bluedist[0] = 0\n",
    "        for a, b in redEdges:\n",
    "            rede[a].append(b)\n",
    "\n",
    "        for a, b in blueEdges:\n",
    "            bluee[a].append(b)\n",
    "\n",
    "        for _ in range(n-1):\n",
    "            for i in range(n):\n",
    "                for nei in rede[i]:\n",
    "                    reddist[nei] = min(reddist[nei], bluedist[i]+1)\n",
    "                for nei in bluee[i]:\n",
    "                    bluedist[nei] = min(bluedist[nei], reddist[i]+1)\n",
    "        # print(rede)\n",
    "        # print(bluee)\n",
    "        # print(reddist)\n",
    "        # print(bluedist)\n",
    "        ret = [float('inf')]*n\n",
    "        for i in range(n):\n",
    "            r = min(reddist[i], bluedist[i])\n",
    "            if r == float('inf'):\n",
    "                ret[i] = -1\n",
    "            else:\n",
    "                ret[i] = r\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: BFS\n",
    "    time: O(n+r+b), where r = numbers of rededge, b = numbers of blueedges,\n",
    "    space: O(n+r+b) for <red_graph>, <blue_graph>, O(n) for <queue>,\n",
    "        totally, O(n^2).\n",
    "    \"\"\"\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red_graph = collections.defaultdict(list)\n",
    "        blue_graph = collections.defaultdict(list)\n",
    "\n",
    "        for a, b in redEdges:\n",
    "            red_graph[a].append(b)\n",
    "        for u, v in blueEdges:\n",
    "            blue_graph[u].append(v)\n",
    "\n",
    "        answer = [-1 for _ in range(n)]\n",
    "        queue = [(0, 0, None)]  # [(node, distance, prev_color), ...]  color: 0-red 1-blue\n",
    "        visited = set()\n",
    "        visited.add((0, None))  # {(node, prev_color), ...}\n",
    "        while queue:\n",
    "            node, dist, color = queue.pop(0)\n",
    "            if answer[node] == -1:\n",
    "                answer[node] = dist\n",
    "\n",
    "            if color != 0:  # color = blue or None\n",
    "                for child in blue_graph[node]:\n",
    "                    if (child, 0) not in visited:\n",
    "                        queue.append((child, dist+1, 0))\n",
    "                        visited.add((child, 0))\n",
    "\n",
    "            if color != 1:  # color = red or None\n",
    "                for child in red_graph[node]:\n",
    "                    if (child, 1) not in visited:\n",
    "                        queue.append((child, dist+1, 1))\n",
    "                        visited.add((child, 1))\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        res = [-1] * n\n",
    "        res[0] = 0\n",
    "        blue = [[] for _ in range(n)]\n",
    "        red = [[] for _ in range(n)]\n",
    "        rv,bv = {0},{0}\n",
    "        for x,y in blueEdges:\n",
    "            blue[x].append(y)\n",
    "        for x,y in redEdges:\n",
    "            red[x].append(y)\n",
    "        for p in red[0]:\n",
    "            q.put([p,1,'r'])\n",
    "            rv.add(p)\n",
    "        for p in blue[0]:\n",
    "            q.put([p,1,'b'])\n",
    "            bv.add(p)\n",
    "        while not q.empty():\n",
    "            e,l,c = q.get()\n",
    "            curNode = e\n",
    "            if res[curNode] == -1 or res[curNode] > l:\n",
    "                res[curNode] = l\n",
    "            if c == \"r\":\n",
    "                for p in blue[e]:\n",
    "                    if p not in bv:\n",
    "                        q.put([p,l+1,\"b\"])\n",
    "                        bv.add(p)\n",
    "            else:\n",
    "                for p in red[e]:\n",
    "                    if p not in rv:\n",
    "                        q.put([p,l+1,'r'])\n",
    "                        rv.add(p)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red = [set() for i in range(n)]\n",
    "        blue = [set() for i in range(n)]\n",
    "        for (x,y) in redEdges:\n",
    "            red[y].add(x)\n",
    "        for (x,y) in blueEdges:\n",
    "            blue[y].add(x)\n",
    "        #print(red)\n",
    "\n",
    "        answer = [0]\n",
    "        index = []\n",
    "        for i in range(1,n):\n",
    "            #print(i)\n",
    "            result = 10000\n",
    "            for flag in [True,False]:\n",
    "                #print(flag)\n",
    "                Q = [i]\n",
    "                ans = 0\n",
    "                visited = []\n",
    "                while Q!=[]:\n",
    "                    index = []\n",
    "                    while Q!=[]:\n",
    "                        #print(Q,result,flag,visited)\n",
    "                        k = Q[0]\n",
    "                        \n",
    "                        if k == 0:\n",
    "                            index = []\n",
    "                            result = min(ans,result)\n",
    "                            break\n",
    "                        \n",
    "                        Q.pop(0)\n",
    "                        if flag==True:\n",
    "                            for x in red[k]: \n",
    "                                if (x,flag) not in visited:\n",
    "                                    visited.append((x,flag))\n",
    "                                    index.append(x)\n",
    "                        else:\n",
    "                            for x in blue[k]:\n",
    "                                if (x,flag) not in visited:\n",
    "                                    visited.append((x,flag))\n",
    "                                    index.append(x)\n",
    "                    ans += 1      \n",
    "                    flag = bool(1-flag)\n",
    "                    Q = index\n",
    "            #print(i,Q,result)\n",
    "            if result==10000:\n",
    "                answer.append(-1)\n",
    "            else:\n",
    "                answer.append(result)\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        \n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def lookup(self,redEdges, blueEdges,node_direct,path_len,min_zero2node_len):\n",
    "        next_nodes =[]\n",
    "        while len(node_direct) > 0:\n",
    "            if not (any(redEdges) or any(blueEdges)):\n",
    "                return        \n",
    "            n, colour = node_direct.popleft()\n",
    "            #下一通路节点 relation[0]头\n",
    "            if colour:\n",
    "                for i, relation in enumerate(redEdges):\n",
    "                    if relation and n == relation[0] and min_zero2node_len[n][1] != 101:\n",
    "                        min_zero2node_len[relation[1]][0] = min(path_len + 1, min_zero2node_len[relation[1]][0]) #path_len + 1  if min_zero2node_len[relation[1]][0] == None else \n",
    "                        redEdges[i] = []\n",
    "                        next_nodes.append((relation[1], 0))\n",
    "                    # elif relation and n == relation[1] and min_zero2node_len[n][1] != -1:\n",
    "                    #     min_zero2node_len[relation[0]][0] = path_len + 1\n",
    "                    #     redEdges[i] = []\n",
    "                    #     next_nodes.append((relation[0], 0))\n",
    "            else:\n",
    "                for i, relation in enumerate(blueEdges):\n",
    "                    if relation and n == relation[0] and min_zero2node_len[n][0] != 101:\n",
    "                        min_zero2node_len[relation[1]][1] = min(path_len + 1, min_zero2node_len[relation[1]][1]) # path_len + 1  if min_zero2node_len[relation[1]][1] == None else\n",
    "                        blueEdges[i] = []\n",
    "                        next_nodes.append((relation[1], 1))\n",
    "                    # elif relation and n == relation[1] and min_zero2node_len[n][0] != -1:\n",
    "                    #     min_zero2node_len[relation[0]][0] = path_len + 1\n",
    "                    #     blueEdges[i] = []\n",
    "                    #     next_nodes.append((relation[0], 0))\n",
    "        if not next_nodes:\n",
    "            return\n",
    "        node_direct.extend(next_nodes)\n",
    "        path_len += 1\n",
    "        self.lookup(redEdges, blueEdges,node_direct,path_len,min_zero2node_len)    \n",
    "         \n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        min_zero2node_len = [[101,101] for _ in range(n)]\n",
    "        min_zero2node_len[0] = [0,0]\n",
    "        redEdges.sort()\n",
    "        blueEdges.sort()\n",
    "        #node_direct (节点，0红色 1蓝色)\n",
    "        node_direct,path_len  = deque([(0,0),(0,1)]), 0\n",
    "        self.lookup(redEdges, blueEdges,node_direct,path_len,min_zero2node_len)\n",
    "        return  [min(n) if min(n) !=101 else -1 for n in min_zero2node_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def lookup(self,redEdges, blueEdges,node_direct,path_len,min_zero2node_len):\n",
    "        next_nodes =[]\n",
    "        while len(node_direct) > 0:\n",
    "            if not (any(redEdges) or any(blueEdges)):\n",
    "                return        \n",
    "            n, colour = node_direct.popleft()\n",
    "            #下一通路节点 relation[0]头\n",
    "            if colour:\n",
    "                for i, relation in enumerate(redEdges):\n",
    "                    if relation and n == relation[0] and min_zero2node_len[n][1] != 101:\n",
    "                        min_zero2node_len[relation[1]][0] = min(path_len + 1, min_zero2node_len[relation[1]][0]) \n",
    "                        redEdges[i] = []\n",
    "                        next_nodes.append((relation[1], 0))\n",
    "\n",
    "            else:\n",
    "                for i, relation in enumerate(blueEdges):\n",
    "                    if relation and n == relation[0] and min_zero2node_len[n][0] != 101:\n",
    "                        min_zero2node_len[relation[1]][1] = min(path_len + 1, min_zero2node_len[relation[1]][1]) \n",
    "                        blueEdges[i] = []\n",
    "                        next_nodes.append((relation[1], 1))\n",
    "\n",
    "        if not next_nodes:\n",
    "            return\n",
    "        node_direct.extend(next_nodes)\n",
    "        path_len += 1\n",
    "        self.lookup(redEdges, blueEdges,node_direct,path_len,min_zero2node_len)    \n",
    "         \n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        min_zero2node_len = [[101,101] for _ in range(n)]\n",
    "        min_zero2node_len[0] = [0,0]\n",
    "        #redEdges.sort()\n",
    "        #blueEdges.sort()\n",
    "        #node_direct (节点，0红色 1蓝色)\n",
    "        node_direct,path_len  = deque([(0,0),(0,1)]), 0\n",
    "        self.lookup(redEdges, blueEdges,node_direct,path_len,min_zero2node_len)\n",
    "        return  [min(n) if min(n) !=101 else -1 for n in min_zero2node_len]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        dr = {i: set() for i in range(n)}\n",
    "        db = {i: set() for i in range(n)}\n",
    "        for i, j in redEdges:\n",
    "            dr[i].add(j)\n",
    "        for i, j in blueEdges:\n",
    "            db[i].add(j)\n",
    "\n",
    "        m = [-1]*n\n",
    "        m[0] = 0\n",
    "        r = n-1\n",
    "\n",
    "        rc = [[True]*n for _ in range(2)]\n",
    "        rc[0][0] = rc[1][0] = False\n",
    "\n",
    "        s = 0\n",
    "        q = [[0, 0, 1, 0], [0, 1, 0, 1]]\n",
    "        while q:\n",
    "            s += 1\n",
    "            q1 = []\n",
    "            for j, c, hr, hb in q:\n",
    "                d, h = (dr, hr) if c else (db, hb)\n",
    "                l = [hr, hb]\n",
    "                for k in d[j]:\n",
    "                    if rc[not c][k] and not h & 2**k:\n",
    "                        rc[not c][k] = False\n",
    "                        l[not c] = h|2**k\n",
    "                        q1.append([k, not c]+l)\n",
    "                        if m[k] == -1:\n",
    "                            m[k] = s\n",
    "                            r -= 1\n",
    "                            if r == 0:\n",
    "                                return m \n",
    "            q = q1\n",
    "                \n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * n\n",
    "        que = []\n",
    "        reds = dict()\n",
    "        blues = dict()\n",
    "        for chu, ru in redEdges:\n",
    "            if chu in reds:\n",
    "                reds[chu].append(ru)\n",
    "            else:\n",
    "                reds[chu] = [ru]\n",
    "        for chu, ru in blueEdges:\n",
    "            if chu in blues:\n",
    "                blues[chu].append(ru)\n",
    "            else:\n",
    "                blues[chu] = [ru]\n",
    "        len_path = 0\n",
    "        vis = set()\n",
    "        que.append((0, 1))\n",
    "        que.append((0, 0))\n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                i, c = que.pop(0)\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = len_path\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                if c:\n",
    "                    if i in reds:\n",
    "                        for j in reds[i]:\n",
    "                            if (j, c) not in vis:\n",
    "                                que.append((j, c))\n",
    "                else:\n",
    "                    if i in blues:\n",
    "                        for j in blues[i]:\n",
    "                            if (j, c) not in vis:\n",
    "                                que.append((j, c))\n",
    "            len_path += 1\n",
    "        return ans\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        redge = defaultdict(list)\n",
    "        bedge = defaultdict(list)\n",
    "        for x, y in redEdges:\n",
    "            redge[x].append(y)\n",
    "        for x, y in blueEdges:\n",
    "            bedge[x].append(y)\n",
    "\n",
    "        ans = [-1] * n \n",
    "        rvisit = [False] * n\n",
    "        bvisit = [False] * n\n",
    "        step = 0\n",
    "        q = deque([(0, 1, 0), (0, 0, 0)])\n",
    "        ans = [-1] * n\n",
    "        while q:\n",
    "            node, flag, step = q.popleft()\n",
    "            ans[node] = step if ans[node] == -1 else ans[node]\n",
    "            if flag == 0:\n",
    "                rvisit[node] = True\n",
    "                for b in bedge[node]:\n",
    "                    if not bvisit[b] : \n",
    "                        q.append((b, 1, step + 1)) \n",
    "            elif flag == 1:\n",
    "                bvisit[node] = True\n",
    "                for r in redge[node]:\n",
    "                    if not rvisit[r]:\n",
    "                        q.append((r, 0, step + 1)) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        r = defaultdict(list)\n",
    "        b = defaultdict(list)\n",
    "        for e in redEdges:\n",
    "            r[e[0]].append(e[1])\n",
    "        for e in blueEdges:\n",
    "            b[e[0]].append(e[1])\n",
    "        r_visit = set()\n",
    "        b_visit = set()\n",
    "        q = deque()\n",
    "        #注意第二位的0，1代表这点后的线应该是什么颜色的！\n",
    "        q.append([0,0])\n",
    "        q.append([0,1])\n",
    "        r_visit.add(0)\n",
    "        b_visit.add(0)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(-1)\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                node, color = q.popleft()\n",
    "                if ans[node] < 0:\n",
    "                    ans[node] = step\n",
    "                else:\n",
    "                    ans[node] = min(ans[node], step)\n",
    "                if color == 0:\n",
    "                    for nxt in r[node]:\n",
    "                        if nxt in r_visit:\n",
    "                            continue\n",
    "                        r_visit.add(nxt)\n",
    "                        q.append([nxt,1])\n",
    "                if color == 1:\n",
    "                    for nxt in b[node]:\n",
    "                        if nxt in b_visit:\n",
    "                            continue\n",
    "                        b_visit.add(nxt)\n",
    "                        q.append([nxt,0])\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph_red = {}\n",
    "        graph_blue = {}\n",
    "        for fo, to in redEdges:\n",
    "            if fo not in graph_red:\n",
    "                graph_red[fo] = set()\n",
    "            graph_red[fo].add(to)\n",
    "        for fo, to in blueEdges:\n",
    "            if fo not in graph_blue:\n",
    "                graph_blue[fo] = set()\n",
    "            graph_blue[fo].add(to)\n",
    "\n",
    "        res = [float('inf') for _ in range(n)]\n",
    "        res[0] = 0\n",
    "        node1 = (0, 0, 'r')\n",
    "        node2 = (0, 0, 'b')\n",
    "        q = deque([])\n",
    "        q.append(node1)\n",
    "        q.append(node2)\n",
    "        seen = set([(0,'r'), (0, 'b')])\n",
    "        while q:\n",
    "            node, cost, color = q.popleft()\n",
    "            if color == 'r':\n",
    "                for next_node in graph_blue.get(node, []):\n",
    "                    if (next_node, 'b') not in seen:\n",
    "                        res[next_node] = min(res[next_node], cost + 1)\n",
    "                        seen.add((next_node, 'b'))\n",
    "                        q.append((next_node, cost + 1, 'b'))\n",
    "            else:\n",
    "                for next_node in graph_red.get(node, []):\n",
    "                    if (next_node, 'r') not in seen:\n",
    "                        res[next_node] = min(res[next_node], cost + 1)\n",
    "                        seen.add((next_node, 'r'))\n",
    "                        q.append((next_node, cost + 1, 'r'))\n",
    "        for i in range(n):\n",
    "            if res[i] == float('inf'):\n",
    "                res[i] = -1\n",
    "        return res\n",
    "\n",
    "                    \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "\n",
    "        res = [-1] * n\n",
    "        q = [[0, 0], [0, 1]]\n",
    "        visited = set()\n",
    "        level = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, color = q.pop(0)\n",
    "                if res[i] == -1:\n",
    "                    res[i] = level\n",
    "                visited.add((i, color))\n",
    "                color ^= 1\n",
    "                for j in g[color][i]:\n",
    "                    if (j, color) not in visited:\n",
    "                        q.append([j, color])\n",
    "            level += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestAlternatingPaths(\n",
    "#         self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "#     ) -> List[int]:\n",
    "#         # g[color][i]\n",
    "#         g = [defaultdict(list), defaultdict(list)]\n",
    "#         for i, j in redEdges:\n",
    "#             # 0 代表红色\n",
    "#             g[0][i].append(j)\n",
    "\n",
    "#         for i, j in blueEdges:\n",
    "#             # 1 代表蓝色\n",
    "#             g[1][i].append(j)\n",
    "\n",
    "#         # [i, color]\n",
    "#         visited = set()\n",
    "#         res = [-1] * n\n",
    "#         level = 0 # 层数\n",
    "#         q = [[0, 0], [0, 1]]  # 红蓝都从0开始\n",
    "#         while q:\n",
    "#             for _ in range(len(q)):\n",
    "#                 i, color = q.pop(0)\n",
    "#                 if res[i] == -1:\n",
    "#                     res[i] = level\n",
    "#                 visited.add((i, color))\n",
    "#                 # 红蓝交替\n",
    "#                 color ^= 1\n",
    "#                 for j in g[color][i]:\n",
    "#                     if (j, color) not in visited:\n",
    "#                         q.append([j, color])\n",
    "#             level += 1\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red={}\n",
    "        blue={}\n",
    "        \n",
    "        for i,j in redEdges:\n",
    "            if i not in red:\n",
    "                red[i]=[j]\n",
    "            else:\n",
    "                red[i].append(j)\n",
    "\n",
    "        for i,j in blueEdges:\n",
    "            if i not in blue:\n",
    "                blue[i]=[j]\n",
    "            else:\n",
    "                blue[i].append(j)        \n",
    "\n",
    "        # 0-> red, 1->blue\n",
    "        def bfs(turn):\n",
    "            cnt=0\n",
    "            q= collections.deque([0])\n",
    "\n",
    "            while q:\n",
    "                cur_round = len(q)\n",
    "                cnt=cnt+1\n",
    "                if turn==0:\n",
    "                    candidate=red\n",
    "                else:\n",
    "                    candidate=blue\n",
    "                for _ in range(cur_round):\n",
    "                    cur=q.popleft()\n",
    "                    if cur in candidate:\n",
    "                        for i in candidate[cur]:\n",
    "                            if turn ==0 and cnt<res_b[i]:\n",
    "                                res_b[i]=cnt\n",
    "                                q.append(i)\n",
    "                            if turn ==1 and cnt<res_r[i]:\n",
    "                                res_r[i]=cnt\n",
    "                                q.append(i)\n",
    "                turn=turn^1\n",
    "\n",
    "\n",
    "        res_r=[ float('inf') for i in range(n) ]\n",
    "        res_b=[ float('inf') for i in range(n) ]\n",
    "        res_r[0]=0\n",
    "        res_b[0]=0\n",
    "        bfs(0)\n",
    "        res_1 = [ min(res_r[i],res_b[i])  for i in range(len(res_r)) ]\n",
    "        res_r=[ float('inf') for i in range(n) ]\n",
    "        res_b=[ float('inf') for i in range(n) ]\n",
    "        res_r[0]=0\n",
    "        res_b[0]=0\n",
    "        bfs(1)\n",
    "        res_2 = [ min(res_r[i],res_b[i])  for i in range(len(res_r)) ]     \n",
    "        return  [ min(res_1[i],res_2[i]) if min(res_1[i],res_2[i])<100 else -1 for i in range(len(res_1)) ]\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red_graph = defaultdict(set)\n",
    "        blue_graph = defaultdict(set)\n",
    "\n",
    "        for start, end in redEdges:\n",
    "            red_graph[start].add(end)\n",
    "        \n",
    "        for start, end in blueEdges:\n",
    "            blue_graph[start].add(end)\n",
    "        \n",
    "        distances = defaultdict(lambda:-1)\n",
    "        queue = deque()\n",
    "        visited = set()\n",
    "        # queue with node, is_red, distance\n",
    "        queue.append((0, True, 0))\n",
    "        visited.add((0, True))\n",
    "        queue.append((0, False, 0))\n",
    "        visited.add((0, False))\n",
    "\n",
    "        while queue:\n",
    "            node, is_red, step = queue.popleft()\n",
    "            if node not in distances or step < distances[node]:\n",
    "                distances[node] = step\n",
    "            \n",
    "            if is_red:\n",
    "                for neighbor in blue_graph[node]:\n",
    "                    if (neighbor, False) in visited:\n",
    "                        continue\n",
    "                    queue.append((neighbor, False, step + 1))\n",
    "                    visited.add((neighbor, False))\n",
    "            else:\n",
    "                for neighbor in red_graph[node]:\n",
    "                    if (neighbor, True) in visited:\n",
    "                        continue\n",
    "                    queue.append((neighbor, True, step + 1))\n",
    "                    visited.add((neighbor, True))\n",
    "        \n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            result.append(distances[i])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        # 单源最短路，且权重为1，单源BFS算法\n",
    "        Red = {}\n",
    "        for st,end in redEdges:\n",
    "            if st in Red:\n",
    "                Red[st].append(end)\n",
    "            else:\n",
    "                Red[st] = [end]\n",
    "        Blue = {}\n",
    "        for st,end in blueEdges:\n",
    "            if st in Blue:\n",
    "                Blue[st].append(end)\n",
    "            else:\n",
    "                Blue[st] = [end]\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        startred = [-1]*n\n",
    "        step = 0\n",
    "        visitedred = set()\n",
    "        visitedred.add(0)\n",
    "\n",
    "        visitedblue = set()\n",
    "        visitedblue.add(0)\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 选择红色\n",
    "                node = q.popleft()\n",
    "                if startred[node] == -1:\n",
    "                    startred[node] = step - 1\n",
    "                if step % 2 != 0:\n",
    "                    if node in Red:\n",
    "                        for nxt in Red[node]:\n",
    "                            if nxt not in visitedred:\n",
    "                                visitedred.add(nxt)\n",
    "                                q.append(nxt)\n",
    "                else:\n",
    "                    if node in Blue:\n",
    "                        for nxt in Blue[node]:\n",
    "                            if nxt not in visitedblue:\n",
    "                                visitedblue.add(nxt)\n",
    "                                q.append(nxt)\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        startblue = [-1]*n\n",
    "        step = 0\n",
    "        visitedred = set()\n",
    "        visitedred.add(0)\n",
    "\n",
    "        visitedblue = set()\n",
    "        visitedblue.add(0)\n",
    "        while q:\n",
    "            step += 1\n",
    "            for _ in range(len(q)):\n",
    "                # 选择红色\n",
    "                node = q.popleft()\n",
    "                if startblue[node] == -1:\n",
    "                    startblue[node] = step - 1\n",
    "                if step % 2 == 0:\n",
    "                    if node in Red:\n",
    "                        for nxt in Red[node]:\n",
    "                            if nxt not in visitedred:\n",
    "                                visitedred.add(nxt)\n",
    "                                q.append(nxt)\n",
    "                else:\n",
    "                    if node in Blue:\n",
    "                        for nxt in Blue[node]:\n",
    "                            if nxt not in visitedblue:\n",
    "                                visitedblue.add(nxt)\n",
    "                                q.append(nxt)\n",
    "        # print(startblue,startred)\n",
    "\n",
    "        res = [-1]*n \n",
    "        for i in range(n):\n",
    "            if startblue[i] == -1 and startred[i] == -1:\n",
    "                continue \n",
    "            if startblue[i] != -1 and startred[i] != -1:\n",
    "                res[i] = min(startblue[i],startred[i])\n",
    "                continue\n",
    "            if startblue[i] == -1:\n",
    "                res[i] = startred[i]\n",
    "            if startred[i] == -1:\n",
    "                res[i] = startblue[i]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph=[[[]for _ in range(n)],[[]for _ in range(n)]] #0为红边,1为蓝边\n",
    "        for u,v in redEdges:\n",
    "            graph[0][u].append(v)\n",
    "        for u,v in blueEdges:\n",
    "            graph[1][u].append(v)\n",
    "        q=deque()\n",
    "        q.append([0,0])\n",
    "        q.append([0,1])#color表示之前的颜色\n",
    "        res=[-1]*n\n",
    "        now=0\n",
    "        h=set()\n",
    "        while q:\n",
    "            n=len(q)\n",
    "            for _ in range(n):\n",
    "                source,color=q.popleft()\n",
    "                if res[source]==-1 or now<res[source]:\n",
    "                    res[source]=now\n",
    "                \n",
    "                for v in graph[1-color][source]:\n",
    "                    if (v,1-color) not in h:\n",
    "                        h.add((v,1-color))\n",
    "                        q.append([v,1-color])\n",
    "            \n",
    "\n",
    "            now+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        res = [float('inf') for _ in range(n)]\n",
    "        res[0] = 0\n",
    "\n",
    "        queue = [(0, 0, 'r'), (0, 0, 'b')]\n",
    "        visited = set([(0, 'r'), (0, 'b')])\n",
    "        while queue:\n",
    "            node, cost, color = queue.pop(0)\n",
    "            if color == 'r':\n",
    "                for start, end in redEdges:\n",
    "                    if start == node and (end, 'b') not in visited:\n",
    "                        res[end] = min(res[end], cost+1)\n",
    "                        queue.append((end, cost+1, 'b'))\n",
    "                        visited.add((end, 'b'))\n",
    "            elif color == 'b':\n",
    "                for start, end in blueEdges:\n",
    "                    if start == node and (end, 'r') not in visited:\n",
    "                        res[end] = min(res[end], cost+1)\n",
    "                        queue.append((end, cost+1, 'r'))\n",
    "                        visited.add((end, 'r'))\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            if res[i] == float('inf'):\n",
    "                res[i] = -1\n",
    "        return res\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(\n",
    "        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i, j in redEdges:\n",
    "            g[0][i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        ans = [-1] * n\n",
    "        vis = set()\n",
    "        q = deque([(0, 0), (0, 1)])\n",
    "        d = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                vis.add((i, c))\n",
    "                c ^= 1\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in vis:\n",
    "                        q.append((j, c))\n",
    "            d += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1)) # 0 表示红色，1 表示蓝色\n",
    "        \n",
    "        # 对于边长为1的图而言，广度优先搜索单次累加即可得到起始点到x点路径长度\n",
    "        dist = [-1] * n\n",
    "        que = [(0, 0), (0, 1)]\n",
    "        vis = {(0, 0), (0, 1)}\n",
    "        level = 0\n",
    "        while que:\n",
    "            sz = len(que)\n",
    "            for i in range(sz):\n",
    "                node, color = que[0]\n",
    "                if dist[node] == -1:\n",
    "                    dist[node] = level\n",
    "                for next_node in g[node]:\n",
    "                    if next_node[1] != color and next_node not in vis:\n",
    "                        que.append(next_node)\n",
    "                        vis.add(next_node)\n",
    "                que.pop(0)\n",
    "            level += 1\n",
    "        return dist\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "      red_path_dict, blue_path_dict = defaultdict(list), defaultdict(list)\n",
    "      for i, j in redEdges:\n",
    "        red_path_dict[i].append(j)\n",
    "      for i, j in blueEdges:\n",
    "        blue_path_dict[i].append(j)\n",
    "\n",
    "      dist = [[None, None] for _ in range(n)]\n",
    "      dist[0] = [0, 0]\n",
    "      step = 0\n",
    "      now_red, now_blue = [0], [0]\n",
    "\n",
    "      while len(now_red) != 0 or len(now_blue) != 0:\n",
    "        new_red, new_blue = [], []\n",
    "        step += 1\n",
    "\n",
    "        #blue red blue red\n",
    "        if len(now_blue) != 0:\n",
    "          for point in now_blue:\n",
    "            for nxt_point in red_path_dict[point]:\n",
    "              if dist[nxt_point][0] is None:\n",
    "                new_red.append(nxt_point)\n",
    "                dist[nxt_point][0] = step\n",
    "\n",
    "        #red blue red blue\n",
    "        if len(now_red) != 0:\n",
    "          for point in now_red:\n",
    "            for nxt_point in blue_path_dict[point]:\n",
    "              if dist[nxt_point][1] is None:\n",
    "                new_blue.append(nxt_point)\n",
    "                dist[nxt_point][1] = step\n",
    "\n",
    "        now_red, now_blue = new_red, new_blue\n",
    "\n",
    "      result = [0] + [-1]*(n-1)\n",
    "      for i in range(1, n):\n",
    "        if not dist[i][0] and not dist[i][1]: \n",
    "          continue\n",
    "        elif dist[i][0] and dist[i][1]:\n",
    "          result[i] = min(dist[i][0], dist[i][1])\n",
    "        elif dist[i][0]:\n",
    "          result[i] = dist[i][0]\n",
    "        else:\n",
    "          result[i] = dist[i][1]\n",
    "\n",
    "      return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red_path, blue_path = defaultdict(list), defaultdict(list)\n",
    "        for i, j in redEdges:\n",
    "            red_path[i].append(j)\n",
    "        for i, j in blueEdges:\n",
    "            blue_path[i].append(j)\n",
    "        \n",
    "        # dist[i][0]表示从0到i通过红蓝红蓝走的最短距离，dist[i][1]表示从0到i通过蓝红蓝红走的最短距离\n",
    "        dist = [[None, None] for i in range(n)]\n",
    "        dist[0] = [0, 0]\n",
    "        step = 0\n",
    "        now_red, now_blue = [0], [0] # 下一个可以走的point\n",
    "        \n",
    "        # 找到分别以红边开始和以蓝边开始的两条最短路径\n",
    "        while len(now_red) != 0 or len(now_blue) != 0 :\n",
    "            new_red, new_blue = [], []\n",
    "            step += 1\n",
    "\n",
    "            # 蓝红蓝红\n",
    "            if len(now_blue) != 0:\n",
    "                for point in now_blue:\n",
    "                    for next_point in red_path[point]:\n",
    "                        if dist[next_point][0] is None:\n",
    "                            new_red.append(next_point)\n",
    "                            dist[next_point][0] = step\n",
    "            # 红蓝红蓝\n",
    "            if len(now_red) != 0:\n",
    "                for point in now_red:\n",
    "                    for next_point in blue_path[point]:\n",
    "                        if dist[next_point][1] is None:\n",
    "                            new_blue.append(next_point)\n",
    "                            dist[next_point][1] = step\n",
    "            \n",
    "            now_red, now_blue = new_red, new_blue\n",
    "\n",
    "        # 在这两条最短路径中选择小的，merge成我们的答案\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if dist[i][0] is None and dist[i][1] is None:\n",
    "                ans.append(-1)\n",
    "            elif dist[i][0] is not None and dist[i][1] is not None:\n",
    "                ans.append(min(dist[i][0], dist[i][1]))\n",
    "            elif dist[i][0] is not None:\n",
    "                ans.append(dist[i][0])\n",
    "            else:\n",
    "                ans.append(dist[i][1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        res1 = [-1] * n\n",
    "        res2 = [-1] * n\n",
    "        res = [res1, res2]\n",
    "        vis = [set(),set()]\n",
    "        \n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        for start_color in [0,1]:\n",
    "            q = [0]\n",
    "            cur_color = start_color\n",
    "            level = 0\n",
    "            while q:\n",
    "                level_size = len(q)\n",
    "                while level_size>0:\n",
    "                    x = q.pop(0)\n",
    "                    for y,c in g[x]:\n",
    "                        # print(x,y,c,cur_color)\n",
    "                        if c == cur_color:\n",
    "                            continue\n",
    "                        if (x,y,c) not in vis[start_color]: # not visited\n",
    "                            if res[start_color][y] == -1: # not visited\n",
    "                                res[start_color][y] = level + 1\n",
    "                            q.append(y)\n",
    "                            vis[start_color].add((x,y,c))\n",
    "                    level_size -=1\n",
    "                \n",
    "                cur_color =  1-cur_color\n",
    "                level += 1\n",
    "        merge_res = []\n",
    "        for i in range(n):\n",
    "            if min(res[0][i],res[1][i]) == -1:\n",
    "                merge_res.append(max(res[0][i],res[1][i]))\n",
    "            else:\n",
    "                merge_res.append(min(res[0][i],res[1][i]))\n",
    "        merge_res[0] = 0\n",
    "        return merge_res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: BFS\n",
    "    time: O(n+r+b), where r = len(redEdges), b = len(blueEdges),\n",
    "    space: O(n+r+b) for <red_graph>, <blue_graph>, O(n) for <queue>,\n",
    "        totally, O(n+r+b).\n",
    "    \"\"\"\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        red_graph = collections.defaultdict(list)\n",
    "        blue_graph = collections.defaultdict(list)\n",
    "\n",
    "        for a, b in redEdges:\n",
    "            red_graph[a].append(b)\n",
    "        for u, v in blueEdges:\n",
    "            blue_graph[u].append(v)\n",
    "\n",
    "        answer = [-1 for _ in range(n)]\n",
    "        queue = [(0, 0, None)]  # [(node, distance, prev_color), ...]  color: 0-red 1-blue\n",
    "        visited = set()\n",
    "        visited.add((0, None))  # {(node, prev_color), ...}\n",
    "\n",
    "        while queue:\n",
    "            node, dist, prev_color = queue.pop(0)\n",
    "            if answer[node] == -1:\n",
    "                answer[node] = dist\n",
    "\n",
    "            if prev_color != 0:  # color = blue or None\n",
    "                for child in blue_graph[node]:\n",
    "                    if (child, 0) not in visited:\n",
    "                        queue.append((child, dist+1, 0))\n",
    "                        visited.add((child, 0))\n",
    "\n",
    "            if prev_color != 1:  # color = red or None\n",
    "                for child in red_graph[node]:\n",
    "                    if (child, 1) not in visited:\n",
    "                        queue.append((child, dist+1, 1))\n",
    "                        visited.add((child, 1))\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1.2: BFS (alternative code)\n",
    "    time: O(n+r+b), where r = len(redEdges), b = len(blueEdges),\n",
    "    space: O(n+r+b) for <graph>, O(n) for <queue>,\n",
    "        totally, O(n+r+b).\n",
    "    \"\"\"\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for a, b in redEdges:\n",
    "            graph[a].append((b, 0))  # color: 0-red\n",
    "        for u, v in blueEdges:\n",
    "            graph[u].append((v, 1))  # 1-blue\n",
    "\n",
    "        answer = [-1 for _ in range(n)]\n",
    "        queue = [(0, 0, None)]  # [(node, distance, prev_color), ...]\n",
    "        visited = set()\n",
    "        visited.add((0, None))  # {(node, prev_color), ...}\n",
    "\n",
    "        while queue:\n",
    "            node, dist, prev_color = queue.pop(0)\n",
    "            if answer[node] == -1:\n",
    "                answer[node] = dist\n",
    "            \n",
    "            for child, color in graph[node]:\n",
    "                if color != prev_color and (child, color) not in visited:\n",
    "                    queue.append((child, dist+1, color))\n",
    "                    visited.add((child, color))\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        # 0节点到x节点的最短路径，并且最短路径必须是一条红一条蓝\n",
    "        # 因为是最短路径，所以用bfs\n",
    "        # bfs时记录上一条边是红是蓝，在这一条边只用另一个颜色的边往下遍历\n",
    "        g = [defaultdict(list), defaultdict(list)]\n",
    "        for i,j in redEdges:\n",
    "            g[0][i].append(j)  # i节点连接的所有节点j\n",
    "        for i,j in blueEdges:\n",
    "            g[1][i].append(j)\n",
    "        \n",
    "        ans = [-1]*n\n",
    "        visited = set()  # 保存已经访问过的节点\n",
    "        q = deque([(0,0),(0,1)])  # ()第一个元素表示从节点0开始，第二个元素表示是可以从红边开始数也可以从蓝边开始数\n",
    "        d = 0  # bfs深度\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, c = q.popleft()  # 节点i，颜色c\n",
    "                if ans[i] == -1:\n",
    "                    ans[i] = d\n",
    "                visited.add((i,c))  # 通过c颜色的边到达i节点\n",
    "                c ^= 1  # 变颜色\n",
    "                for j in g[c][i]:\n",
    "                    if (j, c) not in visited:\n",
    "                        q.append((j,c))  # 下一个颜色连接的所有点入队\n",
    "            d +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        route= [[False for _ in range(n)]]\n",
    "        route1 = [False for _ in range(n)]\n",
    "        route.append(route1)\n",
    "        COLOR = [1, 0]\n",
    "        route[0][0] = True\n",
    "        route[1][0] = True\n",
    "        ans[0] = 0\n",
    "        edges = collections.defaultdict(dict)\n",
    "        for rededge in redEdges:\n",
    "            edges[rededge[0]].setdefault(1,[]).append(rededge[1])\n",
    "        for blueedge in blueEdges:\n",
    "            edges[blueedge[0]].setdefault(0,[]).append(blueedge[1])\n",
    "        count = 0\n",
    "        if not edges[0]: return ans\n",
    "        stack = []\n",
    "        for color,value in edges[0].items():\n",
    "            for v in value:\n",
    "                stack.append((color,v))\n",
    "        while stack:\n",
    "            lay = []\n",
    "            count += 1\n",
    "            for node in stack:\n",
    "                color = COLOR[node[0]]\n",
    "                if route[color][node[1]] is False:\n",
    "                    route[color][node[1]] = True\n",
    "                    ans[node[1]] = count if ans[node[1]] == -1 else min(count,ans[node[-1]])\n",
    "                    try:\n",
    "                        for next_node in edges[node[1]][color]:\n",
    "                            lay.append((color,next_node))\n",
    "                    except KeyError: pass\n",
    "            stack = lay\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        NIL, RED, BLUE = -1, 0, 1\n",
    "        # 建图\n",
    "        red, blue = {x: list() for x in range(n)}, {x: list() for x in range(n)}\n",
    "        for u, v in redEdges:\n",
    "            red[u].append(v)\n",
    "        for u, v in blueEdges:\n",
    "            blue[u].append(v)\n",
    "        # BFS\n",
    "        step = 0\n",
    "        ans = [0] + [-1] * (n - 1)\n",
    "        q = deque([(0, NIL)])\n",
    "        # 防止回头\n",
    "        vis = set()\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                u, t = q.popleft() # 从左侧取\n",
    "                if t in [NIL, BLUE]:\n",
    "                    for v in red[u]:\n",
    "                        if (u, v, RED) not in vis:\n",
    "                            q.append((v, RED))\n",
    "                            vis.add((u, v, RED))\n",
    "                if t in [NIL, RED]:\n",
    "                    for v in blue[u]:\n",
    "                        if (u, v, BLUE) not in vis:\n",
    "                            q.append((v, BLUE))\n",
    "                            vis.add((u, v, BLUE))\n",
    "                if u == 2: print(step)\n",
    "                # 未更新过直接赋值 否则设置为较小值\n",
    "                ans[u] = min(ans[u], step) if ans[u] != -1 else step\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:\n",
    "        res1 = [-1] * n\n",
    "        res2 = [-1] * n\n",
    "        res = [res1, res2]\n",
    "        vis = [set(),set()]\n",
    "        \n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in redEdges:\n",
    "            g[x].append((y, 0))\n",
    "        for x, y in blueEdges:\n",
    "            g[x].append((y, 1))\n",
    "\n",
    "        for start_color in [0,1]:\n",
    "            q = [0]\n",
    "            cur_color = start_color\n",
    "            level = 0\n",
    "            while q:\n",
    "                tmp = q\n",
    "                q = []\n",
    "                while tmp:\n",
    "                    x = tmp.pop(0)\n",
    "                    for y,c in g[x]:\n",
    "                        # print(x,y,c,cur_color)\n",
    "                        if c == cur_color:\n",
    "                            continue\n",
    "                        if (x,y,c) not in vis[start_color]: # not visited\n",
    "                            if res[start_color][y] == -1: # not visited\n",
    "                                res[start_color][y] = level + 1\n",
    "                            q.append(y)\n",
    "                            vis[start_color].add((x,y,c))\n",
    "                \n",
    "                cur_color =  1-cur_color\n",
    "                level += 1\n",
    "        merge_res = []\n",
    "        for i in range(n):\n",
    "            if min(res[0][i],res[1][i]) == -1:\n",
    "                merge_res.append(max(res[0][i],res[1][i]))\n",
    "            else:\n",
    "                merge_res.append(min(res[0][i],res[1][i]))\n",
    "        merge_res[0] = 0\n",
    "        return merge_res\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
